# -*- coding: utf-8 -*-

# 给出一个无重叠的 ，按照区间起始端点排序的区间列表
# 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）

# 示例 1:
# 输入: intervals = [[1,3],[6,9]], newInterval = [2,5]
# 输出: [[1,5],[6,9]]

# 示例 2:
# 输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
# 输出: [[1,2],[3,10],[12,16]]
# 解释: 这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[List[int]]
        :type newInterval: List[int]
        :rtype: List[List[int]]
        """
        if not intervals:
            return [newInterval];

        intervals.append(newInterval);
        for i in range(len(intervals)):
            interval = intervals[i];
            if interval[0] < newInterval[0]:
                if i == len(intervals)-1:
                    intervals.append(interval);
                continue;
            intervals.insert(i, newInterval);
            break;

        rtn = [];
        for i in range(len(intervals)):
            interval = intervals[i];
            if not rtn or interval[0] > rtn[-1][1]:
                rtn.append(interval);
            else:
                rtn[-1][1] = max(rtn[-1][1], interval[1]);
        return rtn;

t = Solution();
print t.insert([[1,5]], [2,7]);